package collect;

public class QuickSort {

    private static void swap(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    private static int Partition(int[] arr, int left, int right){
        if (left == right) return left;

        int pivot = (int)(left + Math.random() * (right - left + 1));
        swap(arr, pivot, right);
        int small_idx = left;
        for (int i = small_idx; i < right; i++){
            if (arr[i] < arr[right]) {
                swap(arr, i, small_idx);
                small_idx++;
            }
        }
        swap(arr, small_idx, right);
        return small_idx;
    }

    public static int[] QuickSort(int[] arr, int left, int right){
        if (left < right){
            int pivotIndex = Partition(arr, left, right);
            QuickSort(arr, left, pivotIndex - 1);
            QuickSort(arr, pivotIndex + 1, right);
        }
        return arr;
    }
}
